---
title: 查找算法
description: 顺序查找、折半查找、哈希表
---

## 顺序查找
将待查找的关键字为 key 的元素从头到尾与表中元素进行比较，如果 <RedSpan>中间存在关键字为 key 的元素，则返回成功；否则，则查找失败。</RedSpan>

平均查找长度为 (n+1)/2，时间复杂度为 O(n)。


## 折半查找
只适用于 <RedSpan>待查找序列中的元素是有序排列的情况。</RedSpan>

设 <RedSpan>查找表的元素存储在一维数组r[1...n]中 </RedSpan>，在表中元素 <RedSpan>已经按照关键字递增（或递减）方式排序的情况下，</RedSpan>进行折半查找的方法是：
1. 首先将 <RedSpan>待查找元素的关键字（key）值与表 r 中间位置上（下标为 mid ）记录的关键字进行比较</RedSpan>，若相等，则查找成功。
2. 若 <RedSpan> key > r[mid] ,则说明待查记录只可能在后半个子表 r[mid+1...n] 中</RedSpan>，下一步应在后半个子表中查找；
3. 若 <RedSpan> key < r[mid], 则说明待查记录之可能在前半个子表 r[1...mid-1] 中，</RedSpan>，下一步应该在前半个子表中查找；
4. 重复以上步骤，逐步缩小范围，直到查找成功或子表为空时为止。

要注意两点：<RedSpan>中间值位置求出若为小数，应该向下取整</RedSpan>；中间值已经比较过不相等，在划分下一次比较区间时，<RedSpan>无需将中间值位置再纳入下一次比较区间。</RedSpan>

折半查找的时间复杂度为 O(log2n)

```java
/**
* 二分查找
*/
public static int binarySearch(int[] arr, int key) {
   int low = 0;
   int high = arr.length - 1;
   while (low <= high) {
//     int mid = (low + high) / 2;
       int mid = low+ (high-low)/2;
       if (arr[mid] == key) {
           return mid;
       }else if (arr[mid] < key) {
           low = mid + 1;
       }else {
           high = mid - 1;
       }
   }
   return -1;
}
```

## 哈希查找
哈希表 <RedSpan>通过一个以记录的关键字为自变量的函数（称为哈希函数）得到该记录的存储地址</RedSpan>，所以再哈希表中进行查找操作时，需要 <RedSpan>用同一哈希函数计算得到待查记录的存储地址</RedSpan>，然后到相应的存储单元去获得有关信息再判定查找是否成功。


例如，设关键码序列为 47,34,13,12,52,38,33,27,3 , 哈希表长度为 11， 哈希函数为 Hash(key)= key mod 11 ,则 <br/>
* Hash(47) = 47 mod 11 = 3
* Hash(34) = 34 mod 11 = 1
* Hash(13) = 13 mod 11 = 2
* Hash(12) = 12 mod 11 = 1
* Hash(52) = 52 mod 11 = 8
* Hash(38) = 38 mod 11 = 5
* Hash(33) = 33 mod 11 = 0
* Hash(27) = 27 mod 11 = 5
* Hash(3) = 3 mod 11 = 3

使用线性探测法解决冲突构造的哈希表如下。

<img src="https://wkq-img.oss-cn-chengdu.aliyuncs.com/20241013040807.png"/>

### 哈希冲突解决方法

1. 开放定址法：`Hi=(H(key)+di) % m i=1,2,...k(k<=m-1)`

2. 链地址法：它在查找表的 <RedSpan>每一个记录中增加一个链域</RedSpan>，链域中存放
